//! ## 13. Roman to Integer (easy, string, 双指针)
//! Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.
//!
//! ```txt
//!  Symbol       Value
//!   I             1
//!   V             5
//!   X             10
//!   L             50
//!   C             100
//!   D             500
//!   M             1000
//! ```
//! For example, 2 is written as `II` in Roman numeral, just two one's added together. 12 is written as `XII`, which is simply `X + II`. The number 27 is written as `XXVII`, which is `XX + V + II`.

//! Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:
//!  - `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
//!  - `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
//!  - `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.
//!
//!  #### Example 1:
//!  ```txt
//!  Input: s = "III"
//!  Output: 3
//!  ```
//!  ### 知识点
//!  - Vec 转 HashMap
//!  - 双指针问题

pub struct Solution;
use std::collections::HashMap;

impl Solution {
    /// #### 原理
    /// 使用双指针前后比较决定 sum 加减
    /// #### 流程
    /// 可以先转为 char 数组, 再用 last = 0 , for cur in 1..n 那一套;
    /// 不过没必要先转为数组, 可以直接 for c in s.chars()
    /// sum = 0
    /// last = 0
    /// for c in s.chars() {
    ///     // c_cal 是 c 代表的数值, 从 map 中获取
    ///     if c_val > last {
    ///         // 如果比 last 大, 要减去两次 last, 因为上次不改加 last 的.
    ///         sum += c_val - last -last
    ///     } else {
    ///         sum += c_val
    ///     }
    ///     last = c_val
    /// }
    ///
    /// #### 边界分析
    /// 当字符串是 "" 时已覆盖
    /// #### 复杂度
    /// - 时间复杂度
    ///     - 只需要循环一遍字符串 O(n)
    /// - 空间复杂度
    ///     - 没有额外的开销
    ///
    pub fn solve(s: String) -> i32 {
        let map: HashMap<char, i32> = vec![
            ('I', 1),
            ('V', 5),
            ('X', 10),
            ('L', 50),
            ('C', 100),
            ('D', 500),
            ('M', 1000),
        ]
        .into_iter()
        .collect();
        let mut sum = 0;
        let mut last = 0;
        for c in s.chars() {
            if let Some(&v) = map.get(&c) {
                if v > last {
                    sum += v - last - last;
                } else {
                    sum += v;
                }
                last = v;
            }
        }
        sum
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(Solution::solve(String::from("III")), 3);
        assert_eq!(Solution::solve(String::from("IV")), 4);
        assert_eq!(Solution::solve(String::from("IX")), 9);
        assert_eq!(Solution::solve(String::from("LVIII")), 58);
        assert_eq!(Solution::solve(String::from("MCMXCIV")), 1994);
    }
}
